package _11_整理题目._5_贪心._跳跃游戏;

import org.junit.Test;

/**
 * https://leetcode-cn.com/problems/jump-game-ii/
 *
 * 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 你的目标是使用 最少的跳跃次数 到达数组的最后一个位置。
 * 假设你 总是 可以到达数组的最后一个位置。
 *
 * 思路一：贪心算法
 *
 * 思路二：暴力计算所有步数，取最小
 *
 */
public class _02_一维最小步数 {

    public int jump(int[] nums) {
        int n = nums.length;
        int maxPosition = 0;
        int end = 0;
        int steps = 0;
        for (int i = 0; i < n-1; i++) {
            maxPosition = Math.max(maxPosition, i+nums[i]);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }

    @Test
    public void main() {
        int[] nums = {2,3,1,1,4};
        System.out.println(jump(nums)); // 2
    }

}
